package com.nl.search;

import java.util.Arrays;

public class FindSortedArrayNumberTimes {

	// 找到有序数组中数字K出现的次数

	public static int getKTimes(int[] array, int k) {
		if (array == null || array.length == 0) {
			return -1;
		}
		int firstKIndex = getFirstK(array, k, 0, array.length - 1);
		int lastKIndex = getLastK(array, k, 0, array.length-1);
		if(firstKIndex!=-1 && lastKIndex !=-1){
			return lastKIndex - firstKIndex + 1;
		}
		return 0;
	}

	private static int getFirstK(int[] array, int k, int start, int end) {
		if (array == null || array.length == 0) {
			return -1;
		}
		int mid = (start + end) / 2;
		if (array[mid] == k) {
			if (mid == start || array[mid - 1] != k) {
				return mid;
			}else{
				end = mid -1;
			}
		} else if (array[mid] > k) {
			end = mid-1;
		} else {
			start = mid+1;
		}
		return getFirstK(array, k, start, end);
	}

	private static int getLastK(int[] array, int k, int start, int end) {
		if (array == null || array.length == 0) {
			return -1;
		}
		int mid = (start + end) / 2;
		if (array[mid] == k) {
			if (mid == end || array[mid + 1] != k) {
				return mid;
			}else{
				start = mid+1;
			}
		} else if (array[mid] > k) {
			end = mid -1;
		} else {
			start = mid+1;
		}
		return getLastK(array, k, start, end);
	}
	public static void main(String[] args) {
		
		System.out.println(getKTimes(new int[]{1,2,3,4,5,5,6,7,8,9,11,11,12}, 2));
		System.out.println(getKTimes(new int[]{1,2,3,4,5,5,6,7,8,9,11,11,12}, 5));
		System.out.println(getKTimes(new int[]{1,2,3,4,5,5,6,7,8,9,11,11,12}, 11));
		System.out.println(getKTimes(new int[]{1,2,3,4,5,5,6,7,8,9,11,11,12}, 12));
	}
}
